⟸ pàgina anterior ⟸

Exercici 9 (Tasca 4).

(complement, context-free languages, hard exercise)

El complementari d’un incontextual pot ser incontextual

En general, els llenguatges incontextuals no són tancats per complementació, és a dir, donat un llenguatge incontextual L, no és cert en general que \overline L també sigui incontextual.

Aquest exercici tracta sobre incontextuals el complementari dels quals resulta ser també incontextual.

1. Doneu una gramàtica incontextual inambigua que generi L=\{a^nb^n \mid n\in \mathbb N\} i una gramàtica incontextual que generi \overline L. Podeu fer que la segona sigui inambigua?

   Consell

   Feu servir RACSO per comprovar si la gramàtica que heu proposat per a \overline L és inambigua.

2. Doneu una gramàtica incontextual inambigua que generi L=\{w\in \{a,b\}^* \mid w=w^R\} i una gramàtica incontextual que generi \overline L. Podeu fer que la segona sigui inambigua?

   Consell

   Feu servir RACSO per comprovar si la gramàtica que heu proposat per a \overline L és inambigua.